package B刷题.暴力递归.A回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author wei.zhao
 * @description: 剑指 Offer 38.字符串的排列
 * @date 2022年04月19日 9:13
 */
public class Code03_Permutation {


    /**
     * 注意两点：
     * 1.怎么判断字符已经使用过？使用Boolean数组，而不是使用HashSet记录下所有已经使用过的字符
     * 2.怎样剪枝防止重复？
     */
    public String[] permutation(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        boolean[] boos = new boolean[s.length()];
        List<String> list = process("", chars, boos);
        String[] result = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    private List<String> process(String str, char[] chars, boolean[] boos) {
        if (str.length() == chars.length) {
            return Arrays.asList(str);
        }
        List<String> result = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {
            if (boos[i] || (i != 0 && chars[i - 1] == chars[i] && !boos[i - 1])) {
                continue;
            }
            boos[i] = true;
            List<String> list = process(str + chars[i], chars, boos);
            result.addAll(list);
            boos[i] = false;
        }
        return result;
    }

}
